class Exercise19
{
  public static void main(String args[])
  {
    //int a[][]={{0,1,9,0,0,0,0,0,0},{0,0,8,0,0,3,0,5,0},{0,7,0,6,0,0,0,8,0},{0,0,1,0,0,6,8,0,9},{8,0,0,0,4,0,0,0,7},{9,4,0,0,0,0,0,1,0},{0,0,0,0,0,2,0,0,0},{0,0,0,0,8,0,5,6,1},{0,0,3,7,0,0,0,9,0}};
    int a[][]={{7,0,0,0,0,0,0,0,3},{0,2,0,1,0,0,0,9,0},{0,0,6,0,0,0,8,0,0},{0,5,0,4,0,1,0,0,0},{0,0,0,0,6,0,0,0,0},{0,0,0,5,0,7,0,4,0},{0,0,8,0,0,0,7,0,0},{0,1,0,0,0,4,0,2,0},{3,0,0,0,0,0,0,0,6}};
    //int a[][]={{1,0,0,0,0,0,0,0,4},{0,7,0,0,0,0,0,2,0},{0,0,8,6,0,0,9,0,0},{0,0,3,0,0,8,5,0,0},{0,0,0,9,3,0,0,0,0},{0,0,0,5,0,0,0,1,0},{0,0,9,0,5,0,8,0,0},{0,2,0,0,0,6,0,0,0},{4,0,0,0,0,0,0,0,7}};
    int i,j;
    Matrix matrix=new Matrix(a);
    while(true)
    {
      if(matrix.isTry()) matrix.beTry();//判断是否需要下探，如果需要，下探。

      if(matrix.isBack()&&!matrix.beBack()) 
      {
        System.out.println("该数独共有"+matrix.total+"组解！");
        return;
      } //判断是否需要回溯，如果需要，回溯。     
    }
  }
}

class Matrix
{
  public int id[][];
  public boolean isPossible[][][];
  public int allPossible[][];
  public int possibleNum[][][];
  public int x,y,num[][];//表示第x行，第y列的方格的第k个可能性正在检验。
  private int firstx,firsty;
  private int lastx,lasty;
  public int total;
  Matrix(int a[][])
  {
    id=new int[9][9];
    total=0;
    isPossible=new boolean[9][9][10];
    allPossible=new int[9][9];
    possibleNum=new int[9][9][9];
    num=new int[9][9];
    x=0;y=0;
    int i,j,k,n;
    for(i=0;i<9;i++)
      for(j=0;j<9;j++)
        for(k=0;k<10;k++)
          isPossible[i][j][k]=false;

    for(i=0;i<9;i++)
      for(j=0;j<9;j++)
      {
        id[i][j]=a[i][j];
        if(a[i][j]!=0)
        {
          isPossible[i][j][a[i][j]]=true;
          allPossible[i][j]=1;
          possibleNum[i][j][0]=a[i][j];
        }
      }
    
    for(i=0;i<9;i++)
      for(j=0;j<9;j++)
        if(a[i][j]==0)
        {
          n=0;
          for(k=1;k<10;k++)
          {
            set(i,j,k);
            if(isFit(i,j)==true)
            {
              possibleNum[i][j][n]=k;
              n++;
              isPossible[i][j][k]=true;
            }
            cancelSet(i,j);
          }
          allPossible[i][j]=n;
        }
next:for(i=0;i<9;i++)
      for(j=0;j<9;j++)
      {
        if(allPossible[i][j]!=1)
        {
          firstx=i;
          firsty=j;
          break next;
        }
      }
label:for(i=8;i>=0;i--)
       for(j=8;j>=0;j--)
      {
        if(allPossible[i][j]!=1)
        {
          lastx=i;
          lasty=j;
          break label;
        }
      }
  }
  int set(int i,int j,int value)
  {
    if(allPossible[i][j]!=1)
      id[i][j]=value;
    return value;
  }
  int set(int i,int j)//总是set当前num值。
  {
    if(allPossible[i][j]!=1)
      id[i][j]=possibleNum[i][j][num[i][j]];

    return id[i][j];
  }
  boolean isFit(int a,int b)
  {
    if(allPossible[a][b]==1)
      return true;
    int i,j,l,m;
    for(i=0;i<9;i++)
    {
      if(i!=b&&id[a][i]==id[a][b])
        return false;
      if(i!=a&&id[i][b]==id[a][b])
        return false;
    }
    l=a/3;
    m=b/3;
    for(i=l*3;i<(l+1)*3;i++)
      for(j=m*3;j<(m+1)*3;j++)
        if((i!=a||j!=b)&&id[i][j]==id[a][b])
          return false;
    return true;
  }
  void cancelSet(int i,int j)
  {
    if(allPossible[i][j]!=1)
      id[i][j]=0;
  }
  boolean isBack()
  {
    if(allPossible[x][y]==1||isShow()) 
      return true; 
    return num[x][y]>=allPossible[x][y];
  }
  boolean beBack()
  {
    do
    {
      if(x==firstx&&y==firsty)
        return false;
      num[x][y]=0;
      cancelSet(x,y);
      if(y>0) y--;
      else 
      {
        x--;
        y=8;
      }
    }while(isBack());
    return true;
  }
  boolean isTry()
  {
    if(x==lastx&&y==lasty&&id[x][y]!=0)
      return false;
    if(allPossible[x][y]==1)
      return true;
    return num[x][y]<allPossible[x][y];
  }
  void beTry()
  {
    while(isTry())
    {
      set(x,y);//假设
      if(isFit(x,y))//如果合适
      {
        num[x][y]++;//为下一次该点的假设作准备
        if(x==lastx&&y==lasty)
          return;
        if(y<8) y++;
        else 
        {
          x++;
          y=0;
        }//下探
      }
      else  //不合适，则取消假设
      {
        cancelSet(x,y);
        num[x][y]++;
      } 
    }
  }
  boolean isShow()
  {
    if(x==lastx&&y==lasty&&isFit(x,y))
    {
      total++;
      int i,j;
      System.out.println("此数独的第"+total+"组解：");
      for(i=0;i<9;i++)
      {
        for(j=0;j<9;j++)
          System.out.print(id[i][j]+" ");
        System.out.println();
      }
      System.out.println();
      return true;
    }
    return false;
  }
}